home *** CD-ROM | disk | FTP | other *** search
/ ADA Programming Guide / ADA Programming Guide.iso / ada_gwu / recover.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-01-30  |  18.1 KB  |  756 lines
  1. /*
  2.  * Copyright (C) 1985-1992  New York University
  3.  * 
  4.  * This file is part of the Ada/Ed-C system.  See the Ada/Ed README file for
  5.  * warranty (none) and distribution info and also the GNU General Public
  6.  * License for more details.
  7.  
  8.  */
  9.  
  10. #include "hdr.h"
  11. #include "ada.h"
  12. #include "miscp.h"
  13. #include "prsutilp.h"
  14. #include "followp.h"
  15. #include "actionp.h"
  16. #include "lookupp.h"
  17. #include "pspansp.h"
  18. #include "adalexp.h"
  19. #include "errsp.h"
  20. #include "recoverp.h"
  21.  
  22. /*    Variables needed for scope and secondary recoveries */
  23.  
  24. extern int *open_seq;
  25. /* struct two_pool *closer_toksyms;
  26.  struct two_pool *closer_bottom; */
  27. extern int n_open_seq;
  28. extern int n_closer_toksyms;
  29. extern int nps;
  30.  
  31. extern struct two_pool *closer_toksyms;
  32. extern char *CLOSER_MESSAGE_SYMS();
  33. extern char closer_candidates[13][3][5];
  34.  
  35. #define EQ(s, t) (strcmp(s, t) == 0)
  36.  
  37. char *err_message(int k, struct prsstack *curtok)        /*;err_message*/
  38. {
  39.     /*    Form error message for secondary recovery
  40.      *  The parameter 'k' indicates the point in the parse and state stacks
  41.      *  at which the recovery is being made
  42.      */
  43.  
  44.     char *e_m_s,
  45.     *err_mess;
  46.     /* k is index into state stack (not parse stack because it is off by 1) */
  47.     int pp = stack_size(sta_stack) - k;
  48.     struct prsstack *prs_stack_k = prs_stack;
  49.  
  50.     if (k == 1)
  51.         /* this is case where there is 1 element on the state stack and 
  52.           * the parse stack is empty (i.e. all input is rejected)
  53.           */
  54.         return ("Unexpected input");
  55.  
  56.     while (--pp >= 0)
  57.         prs_stack_k = prs_stack_k-> prev;
  58.  
  59.     if (EQ((err_mess = err_msg_syms(prs_stack_k->symbol)) , "")) {
  60.         int act;
  61.         struct two_pool *sta_stack_k = sta_stack;
  62.         int kk = stack_size(sta_stack) - k;
  63.  
  64.         while (--kk >= 0)
  65.             sta_stack_k = sta_stack_k -> link;
  66.  
  67.         act = action((int)(sta_stack_k->val.state), curtok->symbol);
  68.  
  69.         if (act > NUM_STATES) {
  70.             e_m_s = err_msg_syms(lhs[act - NUM_STATES - 1]);
  71.             return(EQ(e_m_s , "") ? "Unexpected input" : e_m_s);
  72.         }
  73.         else
  74.             return ("Unexpected input");
  75.  
  76.     }
  77.     else
  78.         return (err_mess);
  79. }
  80.  
  81.  
  82. int prs_block(struct two_pool *states, struct two_pool *toks)    /*;prs_block*/
  83. {
  84.     /* This parse checker returns true if the parse blocks and false  if
  85.      * it  does  not  or  if it cannot be determined that it will block.
  86.      * The sequence of states need not be complete, so  it    is  possible
  87.      * for    a  reduction  to use up all the states.     This makes the goto
  88.      * undetermined.  In such a case the FOLLOW set for  the  left    hand
  89.      * side     is  used.  If the next token is not in the follow set, then
  90.      * surely the parse must block eventually, but if it is not, we have
  91.      * to conclude that not blocking is possible.  The value returned is
  92.      * the predicate 'the parse must block if the state  stack  contains
  93.      * states as a suffix and the token sequence contains toks as a pre-
  94.      * fix'.
  95.      */
  96.     int act, red, nolh, n;
  97.     int ts;
  98.     struct two_pool *top_tp;
  99.     struct two_pool *tmp_tp;
  100.     int    cs;
  101.     short    n_states = 1;
  102.  
  103.     ts = toks->val.state;        /* ts frome toks */
  104.     toks = toks->link;
  105.  
  106.     cs = states->val.state;    /* cs = top(states) */
  107.  
  108.     while(1) {    /* while true */
  109.  
  110.         act = action(cs, ts);
  111.  
  112.         if (act == 0)
  113.             return 1;                            /* parse error */
  114.         else if (act < NUM_STATES) {        /* shift action */
  115.             if (toks == (struct two_pool *)0)
  116.                 return 0;
  117.  
  118.             /* tmp_tp = toks; destroys prs_toks!! */    /* for re-use */
  119.             ts = toks->val.state;        /* next token */
  120.             toks = toks->link;
  121.  
  122.             tmp_tp = TALLOC();
  123.             tmp_tp->link = states;
  124.             tmp_tp->val.state = (cs = act);    /* update stateseq */
  125.             states = tmp_tp;
  126.             n_states ++;
  127.         }
  128.         else if ((red = (act - NUM_STATES )) == 0)    /* accept action */
  129.             return 0;
  130.         else {    /* reduce action */
  131.             int nn;
  132.             red --;        /* Adjust for 0 offset arrays */
  133.             nolh = lhs[red];
  134.             n = n_states - rhslen[red] + 1;
  135.             nn = rhslen[red];
  136.             if (n <= 1)
  137.                 return (is_terminal(ts) && !in_FOLLOW(nolh, ts) );
  138.             /* replace rhs states with lhs    
  139.              * states[n] = (cs = action(states(n - 1), nolh));    
  140.              */
  141.  
  142.             if (nn == 0) {
  143.                 tmp_tp = TALLOC();
  144.                 tmp_tp->link = states;
  145.                 states = tmp_tp;
  146.             }
  147.             else if (nn > 1 ) {
  148.                 top_tp = states;
  149.                 while (--nn > 1)
  150.                     states = states->link;
  151.                 tmp_tp = states;
  152.                 states = states->link;
  153.                 TFREE(top_tp, tmp_tp);
  154.             }
  155.             states->val.state = 
  156.               (cs = action((int)(states->link->val.state), nolh));
  157.             /* n_states -= nn; */
  158.             n_states -= rhslen[red] - 1;
  159.         }
  160.     }
  161. }
  162.  
  163. int prs_check(struct two_pool *stateseq, int *tokseq, int n_tokseq)
  164.                                                             /*;prs_check*/
  165. {
  166.     int ts;
  167.     int cs;
  168.     struct two_pool *top_tp;
  169.     struct two_pool *tmp_tp;
  170.     struct two_pool *temp_stateseq;
  171.     int n_temp_stateseq;
  172.     int nsh;
  173.     int red, act;
  174.  
  175.     /* This is just a parser that operates from the token sequence, tokseq.
  176.      * It returns when an error occurrs, an accept occurs, or the sequence
  177.      * of tokens is exhausted.
  178.      */
  179.  
  180.     /* n_tokseq is actually the size of tokseq - 1. It is used as an offset 
  181.      * into tokseq (which starts at zero). However, when the size of tokseq
  182.      * is desired, we use (n_tokseq + 1) 
  183.      */
  184.  
  185.     copystack(stateseq, &temp_stateseq, &n_temp_stateseq);
  186.  
  187.     nsh = 0;                /* Number of tokens shifted */
  188.  
  189.     ts = tokseq[n_tokseq];            /* Top of tokseq    */
  190.     cs = temp_stateseq->val.state;        /* Top of stateseq    */
  191.  
  192.     while(1)    /* while true */
  193.     {
  194.         act = action(cs, ts);
  195.  
  196.         if (act == 0)
  197.             return nsh;            /* parse error */
  198.         else if (act < NUM_STATES)    /* Shift action */
  199.         {
  200.             if ( (++nsh ) >= (n_tokseq + 1))    /*  up shift count */
  201.                 return nsh;    /*  gone far enough */
  202.  
  203.             ts = tokseq[n_tokseq - nsh];    /* next token */
  204.  
  205.             tmp_tp = TALLOC();    /* Update stateseq */
  206.             tmp_tp->val.state = ( cs = act);
  207.             tmp_tp->link = temp_stateseq;
  208.             temp_stateseq = tmp_tp;
  209.         }
  210.         else if ((red = (act - NUM_STATES )) == 0  ) /* accept action */
  211.             return    ((ts == EOFT_SYM) ? (n_tokseq + 1) : nsh);
  212.         else {                    /* reduce action */
  213.             int nn;
  214.             red --;        /* adjust for 0 offset arrays */
  215.             nn = rhslen[red];
  216.  
  217.             /*     replace rhs states with lhs
  218.              *
  219.              *    stateseq(nn..) := [cs := ACTION(stateseq(nn-1), nolh)];        
  220.              *
  221.              *  Since the top element will be replaced, we strip off nn - 1
  222.              *  elements and then replace the top one.
  223.              *  There are 3 cases : 
  224.              *    nn == 0 :    allocate a new top element
  225.              *            for the state stack
  226.              *    nn == 1 :    Leave the top element for
  227.              *            replacement
  228.              *    nn >  1 :    Strip nn - 1 off the stack.
  229.              *            leaving the top element for
  230.              *            replacement
  231.              */
  232.  
  233.             if ( nn == 0 ) {
  234.                 tmp_tp = TALLOC();
  235.                 tmp_tp->link = temp_stateseq;
  236.                 temp_stateseq =     tmp_tp;
  237.             }
  238.             else if (nn > 1) {
  239.                 top_tp = temp_stateseq;
  240.                 while (--nn > 1)
  241.                     temp_stateseq = temp_stateseq->link;
  242.                 tmp_tp = temp_stateseq;
  243.                 temp_stateseq = temp_stateseq->link;
  244.                 TFREE(top_tp, tmp_tp);
  245.             }
  246.  
  247.             /* Replace the top element with the GOTO    */
  248.  
  249.             temp_stateseq->val.state = 
  250.               (cs = action((int)(temp_stateseq->link->val.state), lhs[red]));
  251.         }
  252.     }
  253. }
  254.  
  255. int scope_recovery(int k, int index, int *open_seq)        /*;scope_recovery*/
  256. {
  257.     int exists = 0;
  258.     int open_loc;
  259.     struct prsstack *prstmp;
  260.     int opener;
  261.     struct two_pool *tmp_tp, *saved_tail, *closer_head, *closer_tail;
  262.     struct two_pool *STA_STACK;
  263.     int closer;
  264.     int i, closer_index;
  265.     int kk = k;
  266.     int ind;
  267.     int *tmp_toksyms;
  268.     int n_tmp_toksyms;
  269.     int prs_distance;
  270.     int check_dist;
  271.     int n_closer;
  272.  
  273.     /* The parameter 'k' indicates the portion of the state stack with
  274.      * which the parse check is to be performed. The parameter 
  275.      * 'index' indicates the portion of the parse stack to be used when
  276.      * looking for the next opener to be closed.
  277.      */
  278.  
  279.     /*
  280.      * if not exists ind in [index .. n_open_seq] 
  281.      *                | k >= open_seq(ind) then
  282.      *                        return false;
  283.      * end if;
  284.      *
  285.      *        Assume that no such ind exists. Loop through, looking for
  286.      *        one.
  287.      */
  288. #ifdef EDEBUG
  289.     if (trcopt)
  290.         fprintf(errfile, "AT PROC: scope_recovery(%d, %d, %d)\n", k, index,
  291.           *open_seq);
  292. #endif
  293.  
  294.     for ( ind = index; ind < n_open_seq; ind++ )
  295.         if ( k - 1 >= open_seq[ind]) {
  296.             /* adjust to k-1 because in C version (only), size of
  297.              * parse stack is 1 less than size of state stack
  298.              */
  299.             exists = 1;
  300.             break;
  301.         }
  302.  
  303.     if (!exists)
  304.         return 0;
  305.  
  306.     open_loc = nps - open_seq[ind];
  307.  
  308.  
  309.     for (prstmp = prs_stack; open_loc--; prstmp = prstmp->prev);
  310.     opener = prstmp->symbol;
  311.     /* Keep prstmp for the error message */
  312.  
  313.  
  314.     /* Map opener into an array index */
  315.     opener = open_index(opener);
  316.     /*
  317.      *    closer_candidates := 
  318.      *            { CLOSER_SYMS(j) :
  319.      *                    j in CLOSER_MAP_SYMS(opener)};
  320.      */
  321.  
  322.     /*    (for closer in closer_candidates) */
  323.  
  324.     for (closer = 0    ; closer_candidates[opener][closer][0] != 0; closer++ )
  325.     {
  326. #ifdef EDEBUG
  327.         if (trcopt)
  328.             fprintf(errfile, "opener %d  closer %d  cand: %c\n", opener, closer,
  329.               closer_candidates[opener][closer][0]);
  330. #endif
  331.         /*    
  332.          *   closer_toksyms := closer + closer_toksyms; 
  333.          *
  334.          *    These are then appended onto the end of TOKSYMS.
  335.          *    This will be represented as a linked list of values.
  336.          */
  337.  
  338.         /* First set up the list for closer */
  339.         closer_head = closer_tail = TALLOC();
  340.         closer_head->link = (struct two_pool *)0;
  341.         closer_head->val.state = closer_candidates[opener][closer][0];
  342.         for(i = 1, n_closer = 1; 
  343.           ((closer_candidates[opener][closer][i] != 0) && (i <= 4)); 
  344.           n_closer++, i ++ ) {
  345.             tmp_tp = TALLOC();
  346.             tmp_tp->link = (struct two_pool *)0;
  347.             tmp_tp->val.state = closer_candidates[opener][closer][i];
  348.             closer_tail->link = tmp_tp;
  349.             closer_tail = tmp_tp;
  350.         }
  351.  
  352.         saved_tail = closer_tail;
  353.         closer_tail->link = closer_toksyms;
  354.         closer_toksyms = closer_head;
  355.         n_closer_toksyms += n_closer;
  356.  
  357.         /*    Set tmp_toksyms = TOKSYMS + closer_toksyms */
  358.  
  359.         tmp_toksyms = (int *)emalloc((1 + n_TOKSYMS + n_closer_toksyms)
  360.             * sizeof(int) );
  361.         for (i = 0; i <= n_TOKSYMS; i++)
  362.             tmp_toksyms[i] = TOKSYMS[i];
  363.         n_tmp_toksyms = n_TOKSYMS;
  364.         for (tmp_tp = closer_toksyms; tmp_tp != (struct two_pool *)0;
  365.           tmp_tp=tmp_tp->link )
  366.             tmp_toksyms[++n_tmp_toksyms] = tmp_tp->val.state;
  367.  
  368.  
  369.  
  370.         /* Take the top n_sta_stack - k elements off the state stack, 
  371.          * keeping them so as to be able to restore the stack after the call.
  372.          */
  373.  
  374.         STA_STACK = sta_stack;
  375.  
  376.         kk = (n_sta_stack = stack_size(STA_STACK)) - k;
  377.         while(--kk > 0)
  378.             STA_STACK = STA_STACK->link;
  379.  
  380.         /* prs_distance = 
  381.          *    prs_check(STA_STACK(1 .. k), TOKSYMS + closer_toksyms);
  382.          */
  383.  
  384.         prs_distance = prs_check(STA_STACK, tmp_toksyms, n_tmp_toksyms);
  385.  
  386.         check_dist = n_closer_toksyms;
  387.  
  388.         if ((prs_distance >= (check_dist + MIN_LEN + 1 + BACKUPTOKS))
  389.           || ((prs_distance >= check_dist)
  390.           && (scope_recovery(k, ind + 1, open_seq))) ) {
  391.             Span_s location;
  392.             char    msg[200];
  393.  
  394.             /* opl := PRS_STACK(open_loc);
  395.              * opl := l_span(opl);
  396.              * opl := top(opl);
  397.              */
  398. #ifdef DEBUG
  399.             if (trcopt)
  400.                 fprintf(errfile, "Successful scope recovery\n");
  401. #endif
  402.             location = l_span(prstmp);
  403.             /* CLOSER_MESSAGE_SYMS is indexed by the sum of the values in
  404.              * each closer, where closer is an element of 
  405.              * closer_candidates[opener]. 
  406.              * I.e.     +/closer_candidates[opener][closer]
  407.              */
  408.  
  409.  
  410.             for (i = 0 , closer_index = 0;
  411.               ((i <= 4) && (closer_candidates[opener][closer][i] != 0)); i++)
  412.                 closer_index += closer_candidates[opener][closer][i];
  413.  
  414.             /* ERR_MSGS := [ CLOSER_MESSAGE_SYMS(closer) 
  415.              *   + ' on line ' + str (opl(1)) ] + ERR_MSGS;
  416.              */
  417.             sprintf(msg, "%s on line %d",
  418.               CLOSER_MESSAGE_SYMS(closer_index), location.line );
  419.             syntax_err( LLOC(curtok), RLOC(curtok), msg);
  420.  
  421.             return 1;
  422.         }
  423.         else {
  424.             /*    closer_toksyms(1 .. n_closer) := []; 
  425.              *
  426.              *    Since we saved the head and tail pointers of the list closer,
  427.              *  this can be done by setting closer_toksyms to point to the 
  428.              *  tail's link.
  429.              */
  430.  
  431.             closer_toksyms = saved_tail->link;
  432.             n_closer_toksyms -= n_closer;
  433.         }
  434.     }
  435.  
  436. #ifdef EDEBUG
  437.     if (trcopt)
  438.         fprintf(errfile, "recursive call #2\n");
  439. #endif
  440.     return scope_recovery(k, ind + 1, open_seq);
  441.  
  442. }
  443.  
  444.  
  445. int stack_size(struct two_pool *s)                            /*;stack_size*/
  446. {
  447.     int size = 0;
  448.     struct two_pool *tmp_tp = s;
  449.  
  450.     while (tmp_tp != (struct two_pool *)0) {
  451.         tmp_tp = tmp_tp->link;
  452.         size ++;
  453.     }
  454.     return (size);
  455. }
  456.  
  457. int spell(char *s, char *t)                                        /*;spell*/
  458. {
  459.     /*    spell : return distance between two names    */
  460.     /*  See Kernighan & Pike */
  461.     /*
  462.      *  very rough spelling metric :
  463.      *    0 if strings are identical
  464.      *    1 if two chars are transposed
  465.      *    2 if one char wrong, added or deleted
  466.      *    3 otherwise
  467.      */
  468.     while (*s++ == *t)
  469.         if (*t++ == '\0')
  470.             return 0;        /* exact match */
  471.     if (*--s)    {
  472.         if (*t)        {
  473.             if (s[1] && t[1] && *s == t[1]
  474.               && *t == s[1] && EQ(s + 2, t + 2))
  475.                 return 1;    /* transposition */
  476.             if (EQ(s + 1, t + 1))
  477.                 return 2;    /* 1 char mismatch */
  478.         }
  479.         if (EQ(s + 1, t))
  480.             return 2;  /* extra character */
  481.     }
  482.     if(*t && EQ(s, t + 1))
  483.         return 2;    /* missing character */
  484.     return 3;
  485. }
  486.  
  487. #undef EQ
  488.  
  489. void try_deletion()                                            /*;try_deletion*/
  490. {
  491.     int    u;
  492.     int ct;
  493.     struct cand    *candidate;
  494.  
  495. #ifdef DEBUG
  496.     if (trcopt)
  497.         fprintf(errfile, "Try_deletion called\n");
  498. #endif
  499.  
  500.     if (TOKSYMS[n_TOKSYMS] >= EOFT_SYM) /* do not delete a nonterminal */
  501.         return;
  502.  
  503.     ct = TOKSYMS[n_TOKSYMS--];
  504.  
  505.     u = prs_check(sta_stack, TOKSYMS, n_TOKSYMS) - BACKUPTOKS;
  506. #ifdef DEBUG
  507.     if (trcopt)
  508.         fprintf(errfile, "prs_check returned %d\n", u);
  509. #endif
  510.  
  511.     if (u > MAX_CHECK ) {
  512.         candidate = CANDALLOC();
  513.         candidate->token_sym = ct;
  514.         candidate->backup_toks = BACKUPTOKS;
  515.         candidate->next = (struct cand *)0;
  516.         MAX_CHECK = u;
  517.         cand_clear();
  518.         CANDIDATES[DELETE] = candidate;
  519.         n_CANDIDATES[DELETE] = 1;
  520. #ifdef DEBUG
  521.         if (trcopt)
  522.             fprintf(errfile, "[ %s %d ] ", TOKSTR(ct), u);
  523. #endif
  524.     }
  525.     else if (u == MAX_CHECK ) {
  526.         candidate = CANDALLOC();
  527.         candidate->token_sym = ct;
  528.         candidate->backup_toks = BACKUPTOKS;
  529.         candidate->next = CANDIDATES[DELETE];
  530.         CANDIDATES[DELETE] = candidate;
  531.         n_CANDIDATES[DELETE] ++;
  532. #ifdef DEBUG
  533.         if (trcopt)
  534.             fprintf(errfile, "[ %s %d ] ", TOKSTR(ct), u);
  535. #endif
  536.     }
  537.  
  538. #ifdef DEBUG
  539.     if (trcopt)
  540.         fprintf(errfile, "\n");
  541. #endif
  542.     TOKSYMS[++n_TOKSYMS] =    ct;
  543.  
  544. }
  545.  
  546. void try_insertion()                                    /*;try_insertion*/
  547. {
  548.     int        u;
  549.     short    ct;
  550.     struct cand * candidate;
  551.     struct two_pool *tmp_tp;
  552.  
  553. #ifdef DEBUG
  554.     if (trcopt) {
  555.         fprintf(errfile, "Try Insertion called\n");
  556.         fprintf(errfile, "MAX_CHECK = %d\n", MAX_CHECK);
  557.     }
  558. #endif
  559.     ct = TOKSYMS[n_TOKSYMS];
  560.  
  561.     TOKSYMS[++n_TOKSYMS] = 0;
  562.  
  563.  
  564.     /* (for t in POSS_TOK) */
  565. #ifdef DEBUG
  566.     if (trcopt)
  567.         fprintf(errfile, "Possible inserts : ");
  568. #endif
  569.     tmp_tp = POSS_TOK;
  570.     while(tmp_tp != (struct two_pool *)0) {
  571.         TOKSYMS[n_TOKSYMS] = tmp_tp->val.state;
  572.  
  573.         u = prs_check(sta_stack, TOKSYMS, n_TOKSYMS) - (BACKUPTOKS + 2);
  574.  
  575. #ifdef DEBUG
  576.         if (trcopt)
  577.             fprintf(errfile, " [ %s,%d,%d ] ",
  578.               namelist((int)(tmp_tp->val.state)), u, BACKUPTOKS);
  579. #endif
  580.  
  581.         if (u > MAX_CHECK) {
  582.             MAX_CHECK = u;
  583.             candidate = CANDALLOC();
  584.             candidate->token_sym = tmp_tp->val.state;
  585.             candidate->t3 = ct;
  586.             candidate->backup_toks = BACKUPTOKS;
  587.             candidate->next = (struct cand *)0;
  588.             cand_clear();
  589.             CANDIDATES[INSERT] = candidate;
  590.             n_CANDIDATES[INSERT] = 1;
  591.         }
  592.         else if (u == MAX_CHECK) {
  593.             candidate = CANDALLOC();
  594.             candidate->token_sym = tmp_tp->val.state;
  595.             candidate->t3 = ct;
  596.             candidate->backup_toks = BACKUPTOKS;
  597.             candidate->next = CANDIDATES[INSERT];
  598.             CANDIDATES[INSERT] = candidate;
  599.             n_CANDIDATES [INSERT] ++;
  600.         }
  601.  
  602.         tmp_tp = tmp_tp->link;
  603.     }
  604. #ifdef DEBUG
  605.     if (trcopt)
  606.         fprintf(errfile, "\n");
  607. #endif
  608.  
  609.     n_TOKSYMS--;
  610. #ifdef DEBUG
  611.     if (trcopt)
  612.         fprintf(errfile, "At end, MAX_CHECK = %d\n", MAX_CHECK);
  613. #endif
  614.  
  615. }
  616.  
  617. void try_merge(struct prsstack *tok1, struct prsstack *tok2)    /*;try_merge*/
  618. {
  619.     int    ct, nt;
  620.     int j, u;
  621.     int    new_tok_sym;
  622.     char  *tok1v;
  623.     char  *tok2v;
  624.     char  *newtok;
  625.     struct cand *candidate;
  626.  
  627. #ifdef DEBUG
  628.     if (trcopt)
  629.         fprintf(errfile, "Try_merge called\n");
  630. #endif
  631.  
  632.     ct = TOKSYMS[n_TOKSYMS--];
  633.     nt = TOKSYMS[n_TOKSYMS--];
  634.  
  635.     tok1v = find_name(tok1);
  636.     tok2v = find_name(tok2);
  637.  
  638.     /* Allocate space for the newtok */
  639.     newtok = malloc((unsigned)(strlen(tok1v) + strlen(tok2v) + 2));
  640.     strcpy(newtok, tok1v);
  641.     strcat(newtok, tok2v);
  642.  
  643. #ifdef DEBUG
  644.     if (trcopt) {
  645.         fprintf(errfile, "Trying to merge <%s> and <%s> into <%s>\n",
  646.           tok1v, tok2v, newtok);
  647.         fprintf(errfile, "The new symbol %s in the symbol table\n",
  648.           (name_map(newtok)?"IS":"IS NOT") );
  649.     }
  650. #endif
  651.     if (name_map(newtok))
  652.         new_tok_sym = namemap(newtok, strlen(newtok));
  653.     else
  654.         new_tok_sym = EOFT_SYM;
  655.  
  656.     if (new_tok_sym < EOFT_SYM ) {
  657.  
  658.         TOKSYMS[++n_TOKSYMS] = new_tok_sym;
  659.  
  660.         u = prs_check(sta_stack, TOKSYMS, n_TOKSYMS) - BACKUPTOKS;
  661. #ifdef DEBUG
  662.         if (trcopt)
  663.             fprintf(errfile, " PRS_CHECK returns %d\n", u);
  664. #endif
  665.  
  666.         if (u > MAX_CHECK) {
  667.             candidate = CANDALLOC();
  668.             candidate->token_sym = new_tok_sym;
  669.             candidate->backup_toks = BACKUPTOKS;
  670.             candidate->next = (struct cand *)0;
  671.             MAX_CHECK = u;
  672.             cand_clear();
  673.             CANDIDATES[MERGE] = candidate;
  674.             n_CANDIDATES [MERGE] = 1;
  675.         }
  676.         else if (u == MAX_CHECK ) {
  677.             candidate = CANDALLOC();
  678.             candidate->token_sym = new_tok_sym;
  679.             candidate->backup_toks = BACKUPTOKS;
  680.             candidate->next = CANDIDATES[MERGE];
  681.             CANDIDATES[MERGE] = candidate;
  682.             n_CANDIDATES [MERGE] ++;
  683.         }
  684.  
  685.         j = TOKSYMS[n_TOKSYMS--]; /* dummy j */
  686.     }
  687.  
  688.     TOKSYMS[++n_TOKSYMS]  = nt;
  689.     TOKSYMS[++n_TOKSYMS]  = ct;
  690. }
  691.  
  692. void try_substitution()                                /*;try_substitution*/
  693. {
  694.     int    u;
  695.     short    ct;
  696.     struct two_pool *tmp_tp;
  697.     struct cand *candidate;
  698.  
  699. #ifdef DEBUG
  700.     if (trcopt)
  701.         fprintf(errfile, "try_substitution called\n");
  702. #endif
  703.  
  704.     if (TOKSYMS[n_TOKSYMS]  >= EOFT_SYM) /* do not delete a nonterminal*/
  705.         return;
  706.  
  707.     ct = TOKSYMS[n_TOKSYMS];
  708.  
  709.     /* poss_substs = {}; */
  710.  
  711. #ifdef DEBUG
  712.     if (trcopt)
  713.         fprintf(errfile, "Poss_substs : ");
  714. #endif
  715.     /*(for t in POSS_TOK)    */
  716.     tmp_tp = POSS_TOK;
  717.     while (tmp_tp != (struct two_pool *)0) {
  718.         TOKSYMS[n_TOKSYMS] = tmp_tp->val.state;
  719.         u = prs_check(sta_stack, TOKSYMS, n_TOKSYMS) - (BACKUPTOKS + 1);
  720.  
  721. #ifdef DEBUG
  722.         if (trcopt)
  723.             fprintf(errfile, " [ %s, %d ] ",
  724.               namelist((int)(tmp_tp->val.state)), u);
  725. #endif
  726.         if (u > MAX_CHECK ) {
  727.             candidate = CANDALLOC();
  728.             candidate->token_sym = tmp_tp->val.state;
  729.             candidate->backup_toks = BACKUPTOKS;
  730.             candidate->t3 = ct;
  731.             candidate->next = (struct cand *)0;
  732.             MAX_CHECK = u;
  733.             cand_clear();
  734.             CANDIDATES[SUBST] = candidate;
  735.             n_CANDIDATES[SUBST] = 1    ;
  736.         }
  737.         else if (u == MAX_CHECK ) {
  738.             candidate = CANDALLOC();
  739.             candidate->token_sym = tmp_tp->val.state;
  740.             candidate->backup_toks = BACKUPTOKS;
  741.             candidate->t3 = ct;
  742.             candidate->next = CANDIDATES[SUBST];
  743.             CANDIDATES[SUBST] = candidate;
  744.             n_CANDIDATES [SUBST] ++;
  745.         }
  746.         tmp_tp = tmp_tp->link;
  747.     }
  748. #ifdef DEBUG
  749.     if (trcopt)
  750.         fprintf(errfile, "\n");
  751. #endif
  752.  
  753.     TOKSYMS[n_TOKSYMS] = ct;
  754. }
  755.  
  756.